class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        need = dict()
        window = dict()

        for c in s1:
            need[c] = need.get(c, 0) + 1
        
        valid = 0

        l, r = 0, 0
        while r < len(s2):
            c = s2[r]
            r += 1

            if c in need:
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:
                    valid += 1

            while r - l >= len(s1):
                if valid == len(need):
                    return True
                
                d = s2[l]
                l += 1

                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        
        return False
            

if __name__ == '__main__':
    s = Solution()
    res = s.checkInclusion("hello", "ooolleoooleh")
    print(res)
